'''
求连续子数组最大和

解题思路：利用动态规划法，计算以array[i]结尾的和进行比较 Fn+1 = max（Fn+Fn+1，Fn）
'''
class Solution:
    def FindGreatestSumOfSubArray(self, array):
        # write code here
        max_num, res = 0, array[0]
        for i in array:
            max_num = max(max_num + i, i)
            res = max(max_num, res)
        return res

s = Solution()
print(s.FindGreatestSumOfSubArray([2,8,1,5,9]))
